////////////////////////////////////////////////////////////////////////////////
/*!	\file		c45Generator.cpp
**	\brief		Defines all method declared in C45Generator.hpp
**	\author		Nate Cleveland
**	\date		11/18/2002 3:52:44 PM
**	\par		DESCRIPTION:
**				 This file also includes several other functions
**					- log2. Computes the log2 of a value. asserts that the value
**					is greater then zero.
**					- log2_safe. Checks the value before computing the log2. If
**					the value is 0 will return the value one. If the value is 
**					less then zero will return zero.
**					- PrintExamples and PrintValues. Displays characters to the
**					screen for ease of debugging.
**					- CompairExamples::operator (), used to sort examples while
**					calculating boundries.
**					- CompairExamples::SetIndex. Sets the index to the proper 
**					element in the case vectors used by CompairExamples::
**					operator ().
**					
**	\par		REMARKS:
**					
*/
////////////////////////////////////////////////////////////////////////////////
//#include "C45Generator.hpp"


//#define DTREE_LOG
#ifdef DTREE_LOG
#	define DTREE_LOG_CONSOLE
#	define DTREE_LOG_FILE
#	define DTREE_LOG_SAFE(a)	(a)	 
#else
#	define DTREE_LOG_SAFE(a)	
#endif



////////////////////////////////////////////////////////////////////////////////
//	FUNCTION:	PrintExamples
/*!	\brief		Prints out the size and elements of a example vector.
**	\param		<Adapter>		The adapter type used by the C45Generator.
**	\param		examples		Vector of examples.
**	\param		str				A pntr to string of charaters to display. Defualted
**								 to NULL.
**	\param		outStream		Streamable class used to display characters. Defualted
**								 to std::cout.
**	\return		none
**	\exception	none
**	\par		DESCRIPTION:
**				 Displays the contents of passed vector and optionaly a string of
**				  characters. Will also accept a reference to a class to stream 
**				  the characters out with. Will defualt display to cout.
**
**	\author		Nate Cleveland
**	\date		11/22/2002 10:52:38 AM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
template<typename Example_type>
void PrintExamples(std::vector<Example_type>& examples, char* str = NULL, 
				   std::ostream& outStream = std::cout)
{
	//print out the optional string.
	if(str)
		outStream << str;

	//Display the size.
	outStream << " Size: " << examples.size() << "\n";

	//Display all elements.
	for(unsigned int y = 0 ; y < examples.size() ; y++)
	{
		outStream << y << ": (";
		for(unsigned int z = 0 ; z <examples[y].attributes.size() ; z++)
			outStream << examples[y].attributes[z].value << ", ";
		outStream << ")" << examples[y].result << "\n";
	}
}

////////////////////////////////////////////////////////////////////////////////
//	FUNCTION:	PrintValues
/*!	\brief		Prints out a vector of values in a ( elm0, elm1, ... , elmN) format.
**
**	\param		cases		Vector to display.
**	\param		str			Optional string of characters to display. Defualts NULL.
**	\param		outStream	Optional stream to display the elements with.
**
**	\return		none
**	\exception	none
**	\par		DESCRIPTION:
**				 Displays passed vector to the screen.
**
**	\author		Nate Cleveland
**	\date		11/22/2002 11:01:03 AM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
template <typename _type>
void PrintValues(std::vector<_type>& cases, char* str = NULL, 
				 std::ostream& outStream = std::cout)
{
	//Display the optional string.
	if(str)		
		outStream << str;
	
	//Display each element of the vector.
	for(unsigned int i = 0 ; i < cases.size() ; i++)
		outStream << i << ": " << cases[i] << "\t";
	outStream << "\n";
}
//No value checking, fast and efficient, does use an assert.
////////////////////////////////////////////////////////////////////////////////
//	FUNCTION:	
/*!	\brief		Computes the log2 of a value.
**	\param		value		Floating point value to compute from.
**	\return		The log2 of value.
**	\exception	Asserts that the value is greater then zero.
**	\par		DESCRIPTION:
**				 inline. Compute by doing log10(value) / log2(value).
**	\author		Nate Cleveland
**	\date		11/18/2002 3:55:37 PM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
inline float log2(float value)
{
	static float log10_2 = static_cast<float>(log10(2.0));
	assert(value > 0);
	return static_cast<float>(log10(value) / log10_2);
}

//returns zero if the value is NaN or 1 if the value is infininte
////////////////////////////////////////////////////////////////////////////////
//	FUNCTION:	
/*!	\brief		Calls log2 after checking the validity of the value param
**	\param		value		Floating point value to compute from.
**	\return		The log2 of value. Returns zero if the value is NaN or 1 if the 
**				 value is infininte
**	\exception	none
**	\par		DESCRIPTION:
**				 inline. Compute by calling log2(value).	
**	\author		Nate Cleveland
**	\date		11/18/2002 3:58:32 PM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
inline float log2_safe(float value)
{
	//would return an INF (infinite) error if we called log2.
	if(0 == value) 
		return 1;

	//Would return an NaN (Not a number) error if we called log2.
	else if( 0 > value)
		return 0;

	return log2(value);	
}


////////////////////////////////////////////////////////////////////////////////
/*!	\class		Function object used to compair two example units by the value
**				 of the currently selected index.
**	\brief		SetIndex must be set to the relevelent value before each use of
**				 this object.
**	\author		Nate Cleveland
**	\date		11/14/2002 5:31:46 PM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
template<class Adapter, typename Case_type, typename Example_type>
class CompairExamples
{
protected:
	static unsigned int currIndex;	//!< Index into the case vector for the operator ()
									//!<  method to use.
	
public:
	////////////////////////////////////////////////////////////////////////////////
	//	FUNCTION:	
	/*!	\brief		Sets the index of the case vector for the operator () method to 
	**				 use.
	**	\param		i			New index value.
	**	\return		none
	**	\exception	none
	**	\par		DESCRIPTION:
	**					
	**	\author		Nate Cleveland
	**	\date		11/22/2002 11:29:18 AM
	**	\warning	none
	*/
	////////////////////////////////////////////////////////////////////////////////
	static void			SetIndex(unsigned int i){currIndex = i;}
	static unsigned int	GetIndex(void)			{return currIndex;}
	
	////////////////////////////////////////////////////////////////////////////////
	//	FUNCTION:	
	/*!	\brief		Compairson method the std::sort function can use to order
	**				 example vectors.
	**	\param		a				left hand side of compairson.
	**	\param		b				right hand side of compairson.
	**	\return		none
	**	\exception	none
	**	\par		DESCRIPTION:
	**					
	**	\author		Nate Cleveland
	**	\date		11/22/2002 11:27:28 AM
	**	\warning	SetIndex must be called and properly initialized before every call.
	*/
	////////////////////////////////////////////////////////////////////////////////
	bool operator()(const Example_type&a, const Example_type&b) const
	{
		const std::vector<Case_type>& aCaseVec = Adapter::GetCaseVec(a);
		const std::vector<Case_type>& bCaseVec = Adapter::GetCaseVec(b);
		float aValue = Adapter::GetCaseValue(aCaseVec[currIndex]);
		float bValue = Adapter::GetCaseValue(bCaseVec[currIndex]);

		if(aValue == bValue)
			return Adapter::GetExampleResult(a) < Adapter::GetExampleResult(b);
		return aValue < bValue;
	}
};
template<class Adapter, typename Case_type, typename Example_type>
unsigned int CompairExamples<Adapter, Case_type, Example_type>::currIndex = 0;


////////////////////////////////////////////////////////////////////////////////
//	FUNCTION:	CalcInfo
/*!	\brief		Calculates the Info Gain of a case.
**
**	\param		classFreq			The frequecy of the favored class.
**	\param		exampleCount		Number of examples.
**	\param		caseFreq			Frequency of this case and this example appearing
**									 together.
**	\return		Value computed is returned.
**	\exception	none
**	\par		DESCRIPTION:
**				 See C4.5 by J Ross. Quinlan for details on formula used.	
**	\author		Nate Cleveland
**	\date		11/22/2002 11:56:11 AM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
inline float CalcInfo(float classFreq, float exampleCount, float caseFreq)
{
	float inverseCaseFreq = fabsf(caseFreq - classFreq);
	return static_cast<float>(classFreq/exampleCount * (-(caseFreq/classFreq) * 
	log2_safe(caseFreq/classFreq) -(inverseCaseFreq/classFreq) * 
	log2_safe(inverseCaseFreq/classFreq)));
}


////////////////////////////////////////////////////////////////////////////////
//	FUNCTION:	
/*!	\brief		Finds the split info of the particular class.
**
**	\param		classFreq		Class that is favored.
**	\param		exampleCount	Number of examples.
**
**	\return		Value computed is returned.
**	\exception	none
**	\par		DESCRIPTION:
**				 See C4.5 by J Ross. Quinlan for details on formula used.	
**	\author		Nate Cleveland
**	\date		11/22/2002 11:56:51 AM
**	\warning	none
*/
////////////////////////////////////////////////////////////////////////////////
inline float CalcSplitInfo(float classFreq, float exampleCount)
{
	float inverseClassFreq = fabsf(classFreq - exampleCount);
	return (-classFreq/exampleCount)*log2_safe(classFreq/exampleCount) + 
		   (-inverseClassFreq/exampleCount)*log2_safe(inverseClassFreq/exampleCount);
}




//! See header for documentation.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
C45Generator(RefObj_type& tree, std::vector<Class_type>& classVec)
:m_tree(tree), m_nodePred(LESS_EQUAL), m_classVec(classVec)
{
	//All done in init list.
	//...
}

//! See header for documentation.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
~C45Generator()
{
	//No need to do anything.
	//...
}


//! See header for documentation.
//! Space = O(G + BuildTree)
//! Time  = O(BuildTree)
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
void C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
operator ()(void)
{
	//make sure we have at least 1 example.
	if(Adapter::GetExampleVec(m_tree).size() < 1)
		return;
	

	//if there is already a tree, delete it.
	if(Adapter::GetTreeRootPtr(m_tree))
		delete Adapter::GetTreeRootPtr(m_tree);

	//Create a new node for the root.
	Adapter::GetTreeRootPtrRef(m_tree) = new Adapter::Node_type;

	//Begin recursively building the tree.
	BuildTree(Adapter::GetExampleVec(m_tree), Adapter::GetTreeRootRef(m_tree));
}


//! See header for documentation.
//! where G is sizeof(C45Generator), C is sizeof(all constants).
//! where M ==> numberOfCases, where N ==> number of examples, L ==> Number of Classes
/*!
	Time  = O{
				FindClassFreq()		==> NM + 2M
				+ CaseParse()		==> 2NM + M
				+ CalcBoundries()	==> NM^3 + MN + M^3 + 4M
				+ NM + M			==> NM + M
				+ BuildTree(N)		==> Sum of above.
			}
		  = O{5NM  + NM^3  +  8M + 5NM + NM^3 + 8M}
		  = O{10NM + 2NM^3 + 16M}
		  = O{2NM^3}


	Space = O{
				FindClassFreq()		==> ~
				+ CaseParse()		==> ~
				+ CalcBoundries()	==> G +M^2 + 2M
				+ G + L				==> G + L
				+ BuildTree(N)		==> Sum of above(except G).
			}

		  = O{C + G + M^2 + 2M + L + M^2 + 2M + L + M^2}
		  = O(C + G + 2M^2 + 4M + 2L}
		  = O{G + 2M^2}
*/
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
void C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
BuildTree(ExampleVector_type& examples, Node_type& node)
{
	//During debug display our status to the screen.
	DTREE_LOG_SAFE(using namespace std);
	DTREE_LOG_SAFE(PrintExamples<Example_type>(examples, "Begin Building tree with "));

	////1.0 Class Selection and case clean-up.
	//Find the most common Class
	unsigned int mostFrequentIndex = -1;	//Eventually will hold the index of the most
											// frequent class.

	//Find class freq returns to us the index of the most frequent class. It also fills
	// our sum vector with the frequency of all classes.
	mostFrequentIndex = FindClassFreq(examples);




	//CaseParse will look at all the cases and mark any that are un-needed.
	node.SetPredType(CaseParse(examples));
	m_nodePred = node.GetPredType();
	DTREE_LOG_SAFE(PrintExamples<Example_type>(examples, "After Parsing "));


	//Now, if all of the examples are the same case or if we no longer have any cases
	// to examine select the most frequent class as the result of this node and return.
	if(m_classFreqVec[mostFrequentIndex] >= examples.size() ||
	   !Adapter::GetCaseVec(examples[0]).size())  
	{
		ChooseMostFrequent(node, mostFrequentIndex);
		return ;	
	}
	
	////2.0 Fill out all our boundry related vectors.
	CalculateBoundries(mostFrequentIndex, examples);


	DTREE_LOG_SAFE(cout<<"Class value is"<<m_classVec[mostFrequentIndex]<<" with index of "<<mostFrequentIndex<<endl);
	DTREE_LOG_SAFE(PrintValues(m_boundryVal, "Boundries are "));
		

	////3.0 Case selection
	unsigned int highestInfoGainCaseIndex	= -1;	

	//FindCaseInfo will find the best case, returns its index into the m_caseGainVec.
	highestInfoGainCaseIndex = FindCaseInfo(mostFrequentIndex, examples);


	DTREE_LOG_SAFE(PrintValues(m_caseGainVec, "Case Gains are "));

	//if highestInfoGainCaseIndex is -1, call ChooseMost frequent and return.
	if(highestInfoGainCaseIndex == -1)
	{
		ChooseMostFrequent(node, mostFrequentIndex);
		return ;	
	}


	//set the winning case as our node.
	node.SetCaseIndex(highestInfoGainCaseIndex);
	node.SetCaseValue(m_boundryVal[highestInfoGainCaseIndex]);
	DTREE_LOG_SAFE(cout<<"Node's Case Index "<<highestInfoGainCaseIndex << endl);
	DTREE_LOG_SAFE(cout<<"Node's Case Value "<<m_boundryVal[highestInfoGainCaseIndex]<<endl);
	

	////4.0 Divide our examples into those that go to the left and those that go to the 
	//right. Hand each of those children the relevent vector.
	ExampleVector_type  leftExamples;
	ExampleVector_type rightExamples;

	for(unsigned int i = 0 ; i < examples.size() ; i++)
	{
		DTREE_LOG_SAFE(cout<<"if " << examples[i].attributes[node.GetCaseIndex()].value);
		DTREE_LOG_SAFE(cout<<node.GetPredType()); 
		DTREE_LOG_SAFE(cout<<node.GetCaseValue() << endl);


		if(node.CalcPred(Adapter::GetCaseValue(Adapter::GetCaseVec(examples[i])[node.GetCaseIndex()])))
			leftExamples.push_back(examples[i]);

		else
			rightExamples.push_back(examples[i]);
	}

	//Recurse along the children. Ensure the tree is legal.
	node.SetLeft(new Node_type);
	node.SetRight(new Node_type);
	DTREE_LOG_SAFE(PrintExamples<Example_type>(leftExamples, "Left will be "));
	DTREE_LOG_SAFE(PrintExamples<Example_type>(rightExamples, "Right will be "));


	//By the rules of this implementation of C4.5 No branch can have only one child.
	if(!leftExamples.size() || !rightExamples.size()) 
		throw "Illegal C4.5 Tree structure.";

	//recurse left.
	DTREE_LOG_SAFE(cout << endl << endl << "Left");
	this->BuildTree(leftExamples, *node.GetLeft());

	//recurse right.
	DTREE_LOG_SAFE(cout<<endl << endl << "Right");
	this->BuildTree(rightExamples, *node.GetRight());
	return;
}//end BuildTree


//! See header for documentation.
//! space ==> O(C + G + FindCaseInfo()) ==> O(C + G + M), 
//!   where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  ==> O(M * FindCaseInfo) ==> O(M(NM+M)) ==> O(NM^2 + M^2)
//!   where M ==> numberOfCases, where N ==> number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
unsigned int C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
SelectBestBoundry(unsigned int classIndex, unsigned int caseIndex, 
				  const std::vector<float>& possibleBoundries,
				  ExampleVector_type& examples) throw()
{
	//test for the simple case where there are no boundries or only one.
	if     (possibleBoundries.size() == 0)			//no boundries
		return -1;
	else if(possibleBoundries.size() == 1)			//only one boundry
		return 0;
	
	
	//Defualt the first boundry as the best one. Save its index and infoValue.
	unsigned int currBestIndex = 0;
	float		 currBestVal = FindCaseInfo(classIndex, caseIndex, 
											possibleBoundries[0], examples);

	//loop through each possible boundry and selected the boundry that has
	// the highest info gain.
	for(unsigned int i = 1 ; i < possibleBoundries.size() ; i++)
	{
		//find Case info of this value.
		float currVal = FindCaseInfo(classIndex, caseIndex, 
									 possibleBoundries[i], examples);

		//see if it is larger then the current "best".
		if(currVal > currBestVal)
		{
			currBestVal = currVal;
			currBestIndex = i;
		}//end if
	}//end for.
	return currBestIndex;
}


//! See header for documentation.
//! space ==> O(C + G + M*SelectBestBoundry + 2M) ==> O(C + G + M^2 + 2M)
//!   where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  ==> O(4M + MN + M*SelectBestBoundry()) ==>  O(NM^3 +  MN + M^3 + 4M))
//!   where M ==> numberOfCases, where N ==> number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
void C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
CalculateBoundries(unsigned int classIndex, ExampleVector_type& examples) throw()
{
	DTREE_LOG_SAFE(using namespace std);

	//Save the number of cases for ease of reference later.
	unsigned int caseCount = (Adapter::GetCaseVec(examples[0])).size();

	//Erase any old boundry vals and refill the array.
	m_boundryVal.clear();
	for(unsigned int k = 0 ; k < caseCount; k++)
		m_boundryVal.push_back(0);

	m_boundryLessCount.clear();
	for(unsigned int k = 0 ; k < caseCount; k++)
		m_boundryLessCount.push_back(0);



	//loop through each case...
	for(unsigned int i = 0 ; i < caseCount; i++)
	{	
		std::vector<float>			possibleBoundries; //will be filled with possible 
													   // breaking points for cont. vals.
		std::vector<unsigned int>	possibleIndex;	   //Filled with indexs to above vec.

		//sort the order of the example by ascending values of this cas
		CompairExamples<Adapter, Adapter::Case_type, Adapter::Example_type>::SetIndex(i);
		std::sort(examples.begin(), examples.end(), CompairExamples<Adapter, Adapter::Case_type, Adapter::Example_type>());

		DTREE_LOG_SAFE(PrintExamples<Example_type>(examples, "Examples have been sorted to "));

		//Loop through until we find a point where the results are different.
		unsigned int j = 0;
		for( ; j < examples.size() - 1 ; j++ )
		{
			//see if the results are different.
			if(Adapter::GetExampleResult(examples[j]) != Adapter::GetExampleResult(examples[j+1]))
			{
				//Average the two values the create this boundry.
				float posBoundVal = Adapter::GetCaseValue(Adapter::GetCaseVec(examples[j  ])[i]);
				posBoundVal		 += Adapter::GetCaseValue(Adapter::GetCaseVec(examples[j+1])[i]);
				posBoundVal		 /= 2;

				//Add this to the vector of possible boundries and their indexes.
				possibleBoundries.push_back(posBoundVal);
				possibleIndex.push_back(j);		
			}//end if
		}//end for

		//Examine each of the possiblitites and selected the best one.
		DTREE_LOG_SAFE(PrintValues(possibleBoundries, "Possible Boundries are: "));

		unsigned int boundryIndex = SelectBestBoundry(classIndex, i, possibleBoundries, 
													  examples);

		//SelectBestBoundry will return -1 if it was unable to select a boundry. in that 
		// case we should just pick one.
		if(boundryIndex == -1)
		{
			m_boundryVal[i] = Adapter::GetCaseValue(Adapter::GetCaseVec(examples[j+1])[i]);
			m_boundryLessCount[i] = static_cast<float>(boundryIndex);
		}

		//otherwise set the value that was stated as the best.
		else
		{
			m_boundryVal[i]		  = Adapter::GetCaseValue(Adapter::GetCaseVec(
									examples[possibleIndex[boundryIndex]+1])[i]);
			m_boundryLessCount[i] = static_cast<float>(possibleIndex[boundryIndex]);
		}//end else

		DTREE_LOG_SAFE(cout << "Chosen Boundry is " << m_boundryVal[i]);
		DTREE_LOG_SAFE(cout << endl);
	}//end for
}


//! See header for documentation.
//! space ==> O(C + G + FindCaseInfo()) ==> O(C + G + M)
//!   where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  ==> O(M + FindCaseInfo()) ==> O(NM + 2M)
//!   where M => numberOfCases, where N => number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
unsigned int C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
FindCaseInfo(unsigned int classIndex, ExampleVector_type& examples) throw()
{
	//loop through each case and calculate its caseInfo. Store the resultant
	// value in m_caseGainVec.
	for(unsigned int i = 0 ; i < Adapter::GetCaseVec(examples[0]).size() ; i++)
	{

		//if this case has been marked by the ignore flag, don't bother clac'ing a value.
		if(m_caseGainVec[i] == IGNORE_CASE)
			continue;		

		m_caseGainVec[i] = 	FindCaseInfo(classIndex, i, m_boundryVal[i], examples);
	}//end for

	//Case FindCaseInto_Best to select the best element, it will return the index to it.
	return FindCaseInfo_Best();
}//end C45Generator::FindCaseInfo


//! See header for documentation.
//! space => O(C + G + M), 
//!  where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  => O(NM + M) 
//!   where M => numberOfCases, where N => number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
float C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
FindCaseInfo(unsigned int classIndex, unsigned int caseIndex, float caseBoundryVal, 
			 ExampleVector_type& examples) throw()
{	
	DTREE_LOG_SAFE(using namespace std);
	//Array of how many classes their are.
	float* classInstance = new float[m_classVec.size()];
	memset(classInstance, 0, sizeof(float)*m_classVec.size());
	
	//in relation to this case count up how many instances there are of this class.
	//loop through each class first.
	for(unsigned int j = 0 ; j < m_classVec.size(); j++)
	{
		//next loop though each example and count up how many instances their are of
		// this class that match this element.
		for(unsigned int k = 0 ; k < examples.size() ; k++)
		{
			const std::vector<Adapter::Case_type>& caseVec = Adapter::GetCaseVec(examples[k]);
			
			//see if this case is on the correct side of the boundry...
			if(Node_type::CalcPred(m_nodePred, Adapter::GetCaseValue(caseVec[caseIndex]), 
								   caseBoundryVal))
			{
				//test to see if this result matches our current class.
				if(Adapter::GetExampleResult(examples[k]) == m_classVec[j])
					classInstance[j]+=1;
			}//end if
		}//end for
	}//end for.
	
	DTREE_LOG_SAFE(cout << classInstance[0] << " & " << classInstance[1] <<endl);
	DTREE_LOG_SAFE(cout << "Class Freq: " << classFreq << endl);	
	
	//Used the data we just calclated to figure out the Case info value. We will
	// use the formula on Page 21 of the C4.5 Book by J. Ross Quinlan.
	float caseInfo = 0;
	
	// loop through each of the classes.
	float exampleCount = static_cast<float>(examples.size());
	for(unsigned int i = 0 ; i < m_classVec.size() ; i++)
		caseInfo += CalcInfo(m_classFreqVec[i], exampleCount, classInstance[i]);

	
	//Also factor in the split info.
	float splitInfo = CalcSplitInfo(m_classFreqVec[classIndex], exampleCount);	
	DTREE_LOG_SAFE(cout << "CaseInfo: " << CaseInfo << "Split: " << splitInfo << endl);
	

	delete classInstance;
	return caseInfo / splitInfo;
}//end C45Generator::FindCaseInfo


//! See header for documentation.
//! space ==> O(C + G), 
//!  where G is sizeof(C45Generator), C is sizeof(all constants). 
//!
//! time  => O(M) 
//!   where M => numberOfCases
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
unsigned int C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
FindCaseInfo_Best(void) const throw()
{
	unsigned int bestIndex = 0;

	//loop through each element of the caseGain vector.
	for(unsigned int i = 1 ; i < m_caseGainVec.size() ; i++)
	{
		//test to see if this value is better then the current best.
		if(m_caseGainVec[bestIndex] < m_caseGainVec[i])
			bestIndex = i;
	}

	//last test, see if the best has been marked to be ignored. 
	// if it has return -1;
	return (m_caseGainVec[bestIndex] == IGNORE_CASE) ? -1 : bestIndex;
}

//! See header for documentation
//! space ==> O(C + G), where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  ==> O(NM + M + CheckPred(N)) ==> O(2NM + M)
//!   where M ==> numberOfCases, where N => number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
NodePredicate C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
CaseParse(ExampleVector_type& examples)
{
	//check to see if we need to init the m_caseGain member.
	const std::vector<Adapter::Case_type> exampleCaseVec = Adapter::GetCaseVec(examples[0]);
	if(m_caseGainVec.size() != exampleCaseVec.size())
	{
		//clear out the vector and push in zeros.
		m_caseGainVec.clear();
		for(unsigned int i = 0 ; i < exampleCaseVec.size() ; i++)
			m_caseGainVec.push_back(0);
	}

	//loop through each case number.
	for(unsigned int i = 0 ; i < exampleCaseVec.size() ; i++)
	{
		Adapter::Case_type lastCase;		//Case from prevous loop iteration.
		unsigned int j = 1;					//loop counter.
		bool		allCasesEqual = true;	//if true after loop case is marked

		//loop through each example and examine that case.
		for(lastCase = exampleCaseVec[i] ; j < examples.size() ; j++)
		{
			//if this is ever true this case will not need to be cleaned.
			const Adapter::Case_type currCase = (Adapter::GetCaseVec(examples[j]))[i];
			if(Adapter::GetCaseValue(lastCase) != Adapter::GetCaseValue(currCase))
			{
				allCasesEqual = false;
				break;
			}//end if

			//store this case for next loop.
			lastCase = currCase;
		}//end for	

		//if this is true we need to mark this case.
		if(allCasesEqual)
			m_caseGainVec[i] = IGNORE_CASE;

		//otherwise just set the value to zero.
		else
			m_caseGainVec[i] = 0;
	}//end for

	return CheckPred(examples);
}//end C45Generator::CaseParse

//! See header for documentation.
//! space ==> O(C + G), where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  => O(NM) where M => numberOfCases, where N => number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
NodePredicate C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
CheckPred(const ExampleVector_type& examples)
{
	//loop through all the examples and cases, if any of them are not zero or one 
	// break and return LESS_EQUAL.
	bool isBoolean = true;			//will be set to false if any element is not 0 or 1

	//loop through each example.
	for(unsigned int i = 0 ; i < examples.size() && isBoolean; i++)
	{
		//loop through each element in the current example's case vector.
		for(unsigned int j = 0; j < (Adapter::GetCaseVec(examples[i])).size() && isBoolean; j++)
		{
			//check to see if this element is either not 1 or 0.
			if(Adapter::GetCaseValue(Adapter::GetCaseVec(examples[i])[j]) != 0  &&  
			   Adapter::GetCaseValue(Adapter::GetCaseVec(examples[i])[j]) != 1)
				isBoolean = false;		
		}//end for
	}//end for

	//return EQUAL_TO if all cases were 0 or 1.
	if(isBoolean)
		return EQUAL_TO;
	return LESS_EQUAL;
}


//! See header for documentation.
//! space ==> O(C + G), where G is sizeof(C45Generator), C is sizeof(all constants).
//!
//! time  => O(2M + NM) 
//!   where M => numberOfClasses, where N => number of examples.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
unsigned int C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
FindClassFreq(ExampleVector_type& examples) throw()
{
	//zero out sum vec and set members to zero.
	m_classFreqVec.clear();
	for(unsigned int i = 0 ; i < m_classVec.size() ; i++)
		m_classFreqVec.push_back(0);

	//loop through each example.
	for(unsigned int i = 0 ; i < examples.size() ; i++)
	{
		//loop through each m_classVec element
		for(unsigned int classVecIndex = 0 ; classVecIndex < m_classVec.size() ; classVecIndex++)
		{
			//if the result matches, increment the m_classFreqVec element that matches it.
			if(Adapter::GetExampleResult(examples[i]) == m_classVec[classVecIndex]) 
			{
				m_classFreqVec[classVecIndex]+=1;
				break;
			}//end if				
		}//end for
	}//end for

	//Find the index to most frequent element of the vector we just filled.
	unsigned int mostFrequentIndex = 0;
	for(unsigned int i = 0 ; i < m_classFreqVec.size() ; i++)
	{
		//if this sum is gretaer then the prevous best, store the index.
		if(m_classFreqVec[mostFrequentIndex] < m_classFreqVec[i])
			mostFrequentIndex = i;
	}

	return mostFrequentIndex;		
}


// See header for documentation.
template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
void C45Generator<RefObj_type, Adapter, Node_type, Case_type, Class_type, Example_type>::
ChooseMostFrequent(Node_type& node, unsigned int mostFrequentIndex) throw()
{
	DTREE_LOG_SAFE(using namespace std);
	node.SetClass(m_classVec[mostFrequentIndex]);	//set node to most freq class

	DTREE_LOG_SAFE(cout << "This is node is a leaf... "     << endl);	//debug print out
	DTREE_LOG_SAFE(cout << "Pred:  " << node.GetPredType()  << endl);
	DTREE_LOG_SAFE(cout << "Index: " << node.GetCaseIndex() << endl);
	DTREE_LOG_SAFE(cout << "Value: " << node.GetCaseValue() << endl);
	DTREE_LOG_SAFE(cout << "Class: " << node.GetClass()     << endl);
}




/*
//! See header for documentation.
template<class RefObj_type, class Adapter>>
void C45Generator<RefObj_type, Adapter>::CasePurge(ExampleVector_type& examples, unsigned int index)
{
	//loop through each element and erase the attribute at the posistion of "index".
	for(unsigned int i = 0; i < examples.size(); i++)
		examples[i].attributes.erase(&examples[i].attributes[index]);	
}
*/



/*
//! See header for documentation.
template<class RefObj_type, class Adapter>
float C45Generator<RefObj_type, Adapter>::
FindTreeInfoGain(unsigned int classIndex, float classFreq,
				 const ExampleVector_type& examples) throw()
{
	float treeSize = static_cast<float>(examples.size());
	float TreeInfoGain = 0;

	float logA = log2_safe(classFreq/treeSize);
	float logB = log2_safe(static_cast<float>(fabs(classFreq-treeSize)/treeSize));

	//favored class
	TreeInfoGain += -(classFreq/treeSize) * logA;
	TreeInfoGain += -static_cast<float>(fabs(classFreq-treeSize)/treeSize) * logB;
	return m_treeInfo = TreeInfoGain;
}
*/